1. Field of the Invention
This invention relates to control methods for systems of multiple autonomous or semi-autonomous automatically guided vehicles (AGVs) such as mobile robots and more specifically to a hierarchy of multiple, independently operating, but integrated, software tasks.
2. Description of the Related Art
Conventional automatically guided vehicles (AGVs) such as those used to move materials in warehouses and factories provide minimal (unidirectional) point-to-point movement control. Most such systems involve AGVs which follow a fixed guide track, usually either a radio transmitter antenna wire buried in the factory floor, a reflective stripe painted on the floor, or a reflective tape glued to the floor. Such methods are described in U.S. Pat. Nos. 4530056, 4554724, 4562635, 4593238, and 4593239. All of these schemes purposely limit the individual vehicle's freedom of movement by constraining the AGVs to follow a physically fixed path. These systems typically employ relatively simple control methods which, by virtue of their simplicity, are not very flexible. That is, it is difficult to add or remove vehicles from the system and both difficult and expensive to change the existing pathways.
The majority of multiple-vehicle systems are wire-guided. Guide wires buried in a channel cut in the floor of the factory contain locator strips or cross-wise antennas to provide AGV location information. Sometimes, such systems provide absolute location information by attaching bar-code markers at a fixed height along the path. When an AGV passes such a marker, it "reads" the location from the marker. Wire-guided AGVs detect the location markers via radio reception. Stripe-guided AGVs use optical detectors to sense coded reflective markers. Other AGVs, such as automated forklifts, employ bar-code scanners to decode the location markers. Altering the pathways for any of these systems involves considerable facilities engineering, especially in the case of those which use buried wires.
In such systems, therefore, the individual AGVs are not capable of true point-to-point motion. For example, to drive an AGV to a particular point, the system controller commands it to move until it finds the marker for that point. The AGV effectively is "lost" to the control system until it reaches a location marker. Moreover, the AGV must stay on the physical track, passing each and every intermediate marker in the physically fixed sequence, until it "reads" its destination. There is no external position sensing and reporting system to provide "closed-loop, servo-like" operation.
Since most AGVs are front-drive units, or three-wheeled vehicles similar to tricycles (one steered drive wheel in front, two differentiated trailing wheels at the rear), they have less control when moving in reverse.
Important disadvantages to these systems include: they are limited by closed pathways, by unidirectional motion, by lack of external control of AGV motion, and by lack of independent, real- time control of individual vehicles (i.e., there is no way to redirect Vehicle I directly from Point A to Point X while it is en route to an original destination, say Point M).
There is a growing need for AGV systems with true point-to-point AGV motion, external sensing, real-time communication with individual AGVs, programmable pathways (logical, not physical paths), and modern control computer architectures.
For example, in a typical AGV installation the factory is divided into "blocks." Each block may be an area of the factory wherein AGVs service a given family of machinery. Alternatively, each block could be a separate room in the factory. From a control standpoint, a "block" is simply an area of the factory where only one AGV can operate at a time. This greatly simplifies the control task, but the price extracted by this method may sometimes be too high: no block can use two independently operating AGVs simultaneously. While this may not seem to be a great hardship, consider the reasons for using AGVs in the first place: to improve productivity, to improve personnel safety, and to lower costs. If traditional systems are inflexible, the productivity improvements suffer. As productivity suffers, costs rise.
Solving these problems in traditional AGV systems results in ever more complex control schemes. Blocks may be subdivided into "tracks" or "cells." Once an AGV enters a block, it is Immediately assigned to a subdivision (perhaps one of several rows of machinery or load stations). While such a method frees up the remaining cells, the cost in control complexity and time can be significant in installations with many AGVs.
More modern control methods are used in the Texas Instruments systems, such as those disclosed in Texas Instruments application 10942 (U.S. Ser. No. 771,397), where an external system executive coordinates the tasks of multiple, independently running, computerized control programs which include a communications controller, a central data base, on-board vehicle controllers, a vehicle routing and scheduling controller, and a visual navigation system to provide factory-floor position information updates to free-roving mobile robot AGVs which incorporate on-board dead reckoning. In the TI systems, the AGVs travel within programmable pathways. The AGVs are omnidirectional and can rotate in place; that is, they have a zero turning radius and can move with equal control in any direction. This scheme allows the AGVs to operate in a minimum of pathway space but simultaneously to service a factory layout with maximum efficiency. Furthermore, since the path is not physically attached to the floor, and since the external control scheme can identify the individual AGVs separately, the AGVs can pass each other in any direction, with or without stopping.
Such modern control schemes require three major control system innovations: a modular and hierarchical design for the overall control system; autonomous or semi-autonomous AGVs; and "intelligent" controllers.
"Intelligent" means that the control programs are capable of simultaneous and independent operation. The operating system for the system executive is a real-time, multi-tasking program. These characteristics allow the various parts of the control system to act independently. The central data base concept adds the capability for the independent tasks to access information from other tasks. The effect is to maximize both control (through the hierarchy) and autonomy. Therefore, each independent task must be capable of controlling itself and of interacting with the distributed control system autonomously.